package question0754;

/**
 * @author qianyihui
 * @date 2019-07-11
 *
 * 虽然LeetCode中标注为简单，但其实是一道困难级别的题。
 *
 * 对于target，如果其值为0，1，3，6，10，15，21……，这很容易算，其结果分别是0，1，2，3，4，5，6……
 *
 * （1）那么如果target不为上述值呢？比如，target为17，怎么办呢？
 *
 * 我们的策略是首先找到比17大的那个数，21，其比17大4，4是偶数，那么我们只需要令其中的第2步往左走即可，步数和走到21相同，6步。
 *
 * （2）如果target为18呢，怎么办呢？其比21小3，是奇数，此时我们要看21的下一个数28，其与18差值为10，因此我们只需令其中的第5步往左走即可，
 * 步数和走到28相同，7步。
 *
 * （3）再举一种情况，如果target值为14呢？其比15小1，是奇数，其比21小7，也为奇数，此时我们继续往下找28，比14大14，是偶数，我们只需令其中
 * 第7步往左走即可，共7步。
 *
 * 为什么上述策略所得到的步数是最小步数呢？
 *
 * 对于（1）和（2）中的情况，可以很好理解，那么对于（3）中的情况呢？
 *
 * 14比15小1，不可能存在将某一步调整为左走就能从15变为14的情况，一旦将某一步调整为左走，其变化量一定是偶数。对于21同理，直到28的情况。
 *
 * 时间复杂度是O(target ^ 0.5)。空间复杂度是O(1)。
 *
 * 执行用时：4ms，击败75.58%。消耗内存：34.1MB，击败56.25%。
 */
public class Solution {
    public int reachNumber(int target) {
        if (target < 0) {
            target = -target;
        }
        int index = 0, sum = 0;
        while (sum < target || (sum - target) % 2 != 0) {
            ++index;
            sum += index;
        }
        return index;
    }
}
